package com.ls.linked_list;

/**
 * josefu 约瑟夫环'
 * 环形单向链表
 */
public class CircleLinkedList {

    public static void main(String[] args) {
        CircleLinkedList list = new CircleLinkedList();
        list.addBoy(5);
//        list.show();

        list.countBoy(1,2);
    }

    //初始链表
    private Node first = new Node(-1);
    private int num = -1;

    //创建小孩 链表
    public void addBoy(int num) {

        if (num < 1) {
            return;
        }
        Node tail = null;
        for (int i = 1; i <= num; i++) {
            Node boy = new Node(i);
            if (i == 1) {
                first = boy;
                first.setNext(first);
                tail = first;
                continue;
            }
            tail.setNext(boy);
            boy.setNext(first);
            tail = boy;
        }
        this.num = num;
    }

    public void show() {
        if (first.getNo() == -1) {
            System.out.println("empty");
        }
        Node cur = first;
        while (true) {
            System.out.println(cur);
            if (cur.getNext() == first) {
                break;
            }
            cur = cur.getNext();
        }

    }

    /**
     * @param startNo  表示从第几个小孩开始数数
     * @param countNum 表示数几下
     */
    public void countBoy(int startNo, int countNum) {

        if (first.getNo() == -1 || startNo > num) {
            System.out.println("error");
            return;
        }
        Node helper = first;
        //将helper指向最后节点
        while (true) {
            //说明helper指向最后节点
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        //小孩报数前先让first和helper移动k - 1次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //出圈
        while (true){
            //只剩一个节点
            if (helper == first){
                System.out.println(first.getNo());
                break;
            }
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println(first.getNo());
            first = first.getNext();
            helper.setNext(first);
        }
    }

}

class Node {
    private int no;
    private Node next;

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }
}

